import java.util.ArrayList;

/**
 * An implementation of the classic bubble sort, with runtime {@code &theta
 * (lgn)}
 */

public class BubbleSort
{
    public static ArrayList<Integer> sortInts(ArrayList<Integer> list) {
        boolean swapped = true;
        int count = 0;

        for (int i = 1; i < list.size() && swapped; i++) {
            swapped = false;

            for (int j = 0; j < list.size() - 1; j++) {
                if (list.get(j) > list.get(j + 1)) {
                    int temp = list.get(j);
                    list.set(j, list.get(j + 1));
                    list.set(j + 1, temp);
                    swapped = true;
                }
                count++;
            }
            count++;
        }
        System.out.println("Iterations: " + count);

        return list;
    }

    public static int[] sortInts(int[] list) {
        boolean swapped = true;
        int count = 0;

        for (int i = 1; i < list.length && swapped; i++) {
            swapped = false;

            for (int j = 0; j < list.length - 1; j++) {
                if (list[j] > list[j + 1]) {
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                    swapped = true;
                }
                count++;
            }
            count++;
        }
        System.out.println("Iterations: " + count);

        return list;
    }
}
